#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2019/1/11 10:22
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 高级-寻找重复数.py
# @Software: PyCharm

from utils.main import main, opt_list


class Solution:
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        i = 0
        while True:
            if i >= n:
                break
            x = nums[i]
            if x == i:
                i += 1
                continue
            else:
                if nums[x] == x:
                    return x
                nums[i], nums[x] = nums[x], nums[i]

        return 0


def op(nums):
    solve = Solution()
    print(nums)
    print('ans:', solve.findDuplicate(nums))


def op1():
    nums = [1, 3, 4, 2, 2]
    op(nums)


def op2():
    nums = [3, 1, 3, 4, 2]
    op(nums)


if __name__ == '__main__':
    opt_list.append(op1)
    opt_list.append(op2)
    main()
